講完了Array跟Linked list接下來我們來講Stack跟Queue吧d(`･∀･)b
什麼是Stack勒，先舉一些日常生活中的例子，像是餐廳裡面洗好堆起來的盤子，先洗好的會被放在最下面，最晚被洗好的會在最上面，而我們也會從頂端先拿，就是先拿最晚被洗好的盤子，又或著是折好後跌在衣櫃中的衣服們，先被折好的會被疊在最下面，最晚被折好的會在最上面，也是我們直接拿會先拿到的，這些概念就和Stack很像!!

Stack(堆疊)

特性

• 具有LIFO(Last-In-First-Out)後進先出性質的有序串列
• 插入元素之動作稱為Push
• 刪除元素之動作稱為Pop
• push及pop發生在同一端，稱為頂端(Top)

例: push a, push b, push c, pop, pop, push d

應用

1. 處理副程式呼叫
2. 處理遞迴式呼叫
3. 將算術中之Infix(中序)轉為Postfix(後序)或是Prefix(前序)表示以便執行算術之算
4. Compiler執行Parsing(語法分析)
5. Binary Tree(二元樹)的Inorder(中序遍歷)、Preorder(前序遍歷)、Postorder(後續遍歷)
6. Re-Entrant Routine(可重入)
7. Graph的depth-first-search(深度優先搜尋)
8. 資料反序輸出 例:1,2,3➝3,2,1
9. 取餐盤
10. maze(迷宮)
11. palindrome(回文) 例:abcdcba

抽象資料型別（Abstract Data Type，ADT）

是電腦科學中具有類似行為的特定類別的資料結構的數學模型；或者具有類似語意的一種或多種程式設計語言的資料類型。簡單一點說，在我們設計分析演算法時，不會特別針對某一個演算法特定的資料型態，也不會去考慮實作時的細節及資料本身的性質，而是將資料的一般特性與操作方式一起思考定義出的數學觀念。ADT是一種理論上的觀念，並不局限於任何一種特定的語言，而且每一種ADT都可以透過不同方式實現。今天介紹的Stack就是屬於ADT的一種，之後會介紹到的Queue及Graph、Tree等等也是｡:.ﾟヽ(*´∀`)ﾉﾟ.:｡

Stack的ADT描述

1. stack_create():建立新的堆疊實體
2. stack_push(stack, item):將一個項目堆入堆疊
3. stack_pop(stack):從堆疊頂部取得項目
4. stack_delete(stack):刪除堆疊

Stack的製作

[法一]用array製作

宣告:

1. S:array[1..n] of item;
2. Top:int=0;

• push(S,item) , Time:O(1)

  push(S,item)
  {
      if(Top==n)return "S Full";
      else{
          Top=Top+1;
          S[Top]=item;
          }
   }

• pop(S)➝item , Time:O(1)

  pop(S)➝item
  {
      if(Top==0)return "S empty";
      else{
            item=S[Top];
            Top=Top-1;
            return item;
          }
   }

[法二]用linked list製作

宣告:

1. Node structure
   Data:存資料值
   Link:pointer to next Node
2. Top:pointer=Null;

• push(S,item) , Time:O(1)

  push(S,item)
  {
      ①new(t); //向系統要求一個Node空間
      ②t➝Data = item;
      ③t➝link = Top;
      ④Top = t;
   }

• pop(S)➝item , Time:O(1)

  pop(S)➝item
  {
      if(Top==Null)return "S empty";
      else{
          ①t = Top; //t指向要pop的Node空間
          ②item = Top➝Data;
          ③Top = Top➝link; //Top要往下一個Node跑
          ④free(t); //回收t之Node空間
          return item;
          }
   }

參考資料

ADT維基百科
擁抱「資料結構」的「演算法」(07) - 堆疊 Stack
程式菜鳥自學C++資料結構演算法 – 堆疊Stack介紹與建立